Database Management Systems (DBMS) are among the most widely used information systems. Their importance is unquestioned. The amount of data in DBMS is increasing rapidly. This success is largely due to the simplicity and elegance of the \textit{relational model}. In the relational model \cite{1970codd}, data is stored in relations or simply, tables. In addition to the relational data, other data models have been established over the past decade. With the development of the World Wide Web, the \textit{Extensible Markup Language} (XML) has become a popular data model. In XML, data is stored in a tree-like structure \cite{2008xml, 2006xml}. In recent years yet another data model, \textit{graph databases} \cite{1984kupervardi, 1987kunii}, has gained popularity. Graph databases capture the inherent graph structure of data used in many different applications \cite{2008angles} such as the Semantic Web \cite{2010foundsemweb} as well as social and biological networks \cite{2000GO}. 

The same information is representable in different data models. For example, consider an application that manages information on conference articles. For each article we want to store  the name, the conference proceedings it appeared in, and the year of its publication. The choice of the data model clearly depends on the application. For example, a relational table or database as shown in Figure~\ref{fig:rel_articles} is the most traditional form of data storage. If we aim at a Web-based application an XML document, depicted as a tree in Figure~\ref{fig:xml_articles}, is an option. Another possibility is to use a graph database as shown in Figure~\ref{fig:gdb_articles}. \\

\begin{figure}[t]
\begin{center}
\begin{subfigure}[c]{0.3\textwidth}
\centering
\begin{tabular}{|l|l|l|}
 \hline \multicolumn{1}{|c}{$proc$} & \multicolumn{1}{|c}{$article$} & \multicolumn{1}{|c|}{$year$} \\
 \hline \hline PODS13 & NF & 2013 \\
 \hline PODS13 & DLNF & 2013 \\ \hline
\end{tabular}
\caption{Data stored in a table.}
\label{fig:rel_articles}
\end{subfigure}
\qquad
\begin{subfigure}[c]{0.45\textwidth}
\centering
\begin{tikzpicture}[level distance=12mm,
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize,align=center]
      \Tree [ .$p1$:proc @name\\\textnormal{PODS13} [ .$a1$:article @name\\\textnormal{NF} @year\\\textnormal{2013} ] 
                                                             [ .$a2$:article @name\\\textnormal{DLNF} @year\\\textnormal{2013} ] ]
\end{tikzpicture}
\caption{Data stored in a tree.}
\label{fig:xml_articles}
\end{subfigure}
\begin{subfigure}[c]{\textwidth}
\centering
\input{figures/introduction/01_redundant_information.tikz} 
\caption{Data stored in a graph.}
\label{fig:gdb_articles}
\end{subfigure}
\end{center}
\caption{Information on conference articles stored in different data models.}
\label{fig:articles}
\end{figure}

\noindent Regardless of the data model, the design of a data store is not a trivial task. Database design is a research area of its own and well-studied in the relational model. One of the main questions in database design is: \textit{``How to maintain the consistency of data?''}. This question directly comes into play when we consider consistency in the context of data dependencies, which add semantic information to data. The most prominent kinds of problems associated with data dependencies are the following \cite{1995databases}:

\begin{itemize}
 \item \textit{Incomplete Information}: If one needs to insert incomplete information into a database, this might not be possible due to a data dependency, which leads to an \textit{insertion anomaly}. The deletion of information needed by a data dependency may lead to a \textit{deletion anomaly}.
 \item \textit{Redundancy}: Updates to redundantly stored data must be applied to all instances of it. Updating only one data instance leads to an \textit{update anomaly}.
\end{itemize}

Figure~\ref{fig:articles} shows redundant information in all three data models. Articles that appear in the same conference proceedings should have the same year of publication. For example, the two articles used in Figure~\ref{fig:articles} appeared in the conference proceedings of ``PODS13''. Both were published in 2013. In our simple example, the year is stored redundantly in each data model. Intuitively, this is due to the fact that year is modeled as a ``property'' of each article. Instead, it should be treated as an attribute of conference only. In the following we want to show how we can avoid and repair such redundancies.\\

\noindent For the relational model most of the research to eliminate such problems was conducted in the 1970s \cite{1971codd, 1971codd2}. The \textit{normalization process} \cite{beeri1978} was developed to make data models as redundancy-free as possible. Such models are said to be in a particular \textit{normal form}. Today the most widely used normal form is Boyce-Codd Normal Form (BCNF) \cite{1974codd}.

As we have seen in Figure~\ref{fig:xml_articles}, XML documents may contain redundancies as well. Arenas and Libkin analyzed redundancies in XML data. This led to the introduction of ``A Normal Form for XML documents'' \cite{2002arenas}, called \textit{XML Normal Form} (XNF). They showed that XNF is a faithful extension of BCNF, using a mapping from relational data to XML documents. Under such a mapping, an XML document is in XNF if the underlying relational schema is in BCNF and vice versa.

So far, redundancies in graph databases have not yet been investigated. This thesis aims at filling this gap. Therefore, \textbf{our goal is to introduce a normal form for graph databases}. Graph databases in this normal form avoid the storage of redundant information. Similar to Arenas and Libkin, we want to justify the naturalness of such a normal form as an extension to BCNF. When we translate a relational schema into a graph database we will show that then this graph database is in our new normal form whenever the relational schema is in BCNF and vice versa. \\


\begin{figure}[t]
\begin{center}
\begin{subfigure}[c]{0.45\textwidth}
\centering
\begin{tabular}{|l|l|c|l|l|}
 \cline{1-2} \cline{4-5} \multicolumn{1}{|c|}{$proc$} & \multicolumn{1}{c|}{$article$} & & \multicolumn{1}{c|}{$proc$} & \multicolumn{1}{c|}{$year$} \\
 \cline{1-2}  \cline{4-5}  \cline{1-2} \cline{4-5} PODS13 & NF & & PODS13 & 2013 \\
 \cline{1-2} \cline{4-5} PODS13 & DLNF  \\ \cline{1-2} 
\end{tabular}
\caption{Data stored in tables.}
\label{fig:rel_articles_rep}
\end{subfigure}
\quad
\begin{subfigure}[c]{0.45\textwidth}
\centering
\begin{tikzpicture}[level distance=12mm,
                       edge from parent path={(\tikzparentnode.south) -- (\tikzchildnode.north)}]
      \tikzstyle{every node}=[font=\ttfamily\footnotesize,align=center]
      \Tree [ .$p1$:proc @name\\\textnormal{PODS13} @year\\\textnormal{2013} [ .$a1$:article @name\\\textnormal{NF} ] 
                                                             [ .$a2$:article @name\\\textnormal{DLNF} ] ]
\end{tikzpicture}
\caption{Data stored in a tree.}
\label{fig:xml_articles_rep}
\end{subfigure}
\begin{subfigure}[c]{\textwidth}
\centering
\input{figures/introduction/02_noredundant_information.tikz} 
\caption{Data stored in a graph.}
\label{fig:gdb_articles_rep}
\end{subfigure}
\end{center}
\caption{Information on conference articles stored in different data models.}
\label{fig:articles_rep}
\end{figure}

\noindent In order to achieve this goal, we need to understand the normalization process in the relation model as well as in XML. The success of the normalization process is due to its generality. It does not aim at removing redundant data from a database, but rather it reorganizes the underlying \textbf{structure} to avoid storing redundant information. The structure for relational data is given by a relational schema \cite{1970codd}. A relational schema consists of tables and their columns. Several constraints, known as data dependencies, can be specified to add semantic information to the columns in a table. One type of data dependencies are functional dependencies (FDs). An FD specifies that one or more columns uniquely determine the value of another column in a relation. For example, we can specify that the data in the $proc$ column determines the data in the $year$ column. Such information leads to redundancies. We can then adapt the relational schema to make it redundancy-free. In the example, this means creating an additional table (see Figure~\ref{fig:rel_articles_rep}) that stores the information $year$ together with the $proc$ column.

XML documents can be represented as trees. The structure of these trees is determined by a Document Type Definition (DTD) \cite{2006xml} or some other form of XML schema (eg.\ \cite{2001xsd}). Arenas and Libkin focused on DTDs \cite{2004arenas} and introduced data dependencies over DTDs, called XML Functional Dependencies (XFDs).  XFDs are used to specify that one or more nodes in an XML tree uniquely determine another node. Therefore, XFDs are the analogue to FDs in XML documents. For example, we can specify that the $proc$ element in the tree in Figure~\ref{fig:xml_articles} determines the $year$ attribute of all its $article$ child elements. This leads to redundancies and can be repaired, as depicted in Figure~\ref{fig:xml_articles_rep}, by changing the DTD, such that $year$ is  an attribute of the $proc$ element rather than the $article$ element.

Redundancies in graph databases seen from a relational or XML perspective have not been investigated so far. Several models exist for graph databases. We want to focus on a particular well-suited data model, which should allow us to express constraints over graph databases. Description Logics (DLs) are an ideal choice as a constraint language for graph databases, because their models can be represented as graphs. DLs are a fragment of first-order logic. In DLs there is always a trade-off between expressivity and computational complexity. We are looking for a DL that is expressive enough to allow us to formulate FD-like constraints. For this, $\DLA$ \cite{2006calvanese} is an ideal candidate as a formal model. $\DLA$ is tightly related to conceptual modeling formalisms and is actually able to capture their most important features \cite{2009baader}.  \\

\noindent DLs and especially $\DLA$ already allow to express constraints over the models. But, in order to establish a normal form for $\DLA$ that resembles BCNF and XNF, we need data dependencies that are similar to FDs and XFDs. Therefore, we want to express that one or more nodes in a graph uniquely determine another node. Calvanese et al.\ proposed an extension to $\DLA$, called \textit{path-based identification constraints} \cite{2008calvanese}, that allows such expressions. However, we will show that path-based identification constraints are not powerful enough to capture FDs in DLs. Therefore, we introduce \textit{tree-based identification constraints}. With these constraints we can specify, in the example given in Figure~\ref{fig:gdb_articles}, that every node of type $proc$ determines the node reachable via a path that traverses a ``has\_article'' and an ``appeared'' edge. Such a constraint leads to a redundancy. After moving the ``appeared'' edge to the $proc$ element, the graph-database is redundancy-free. \\


\noindent As we saw in our simple example, redundancies in graph databases can occur when a node is determined by another node, which is reachable via two or more different paths. We will generalize this idea and define a normal form for $\DLA$, called \textit{Description Logic Normal Form} (DLNF).

Since BCNF is the most prominent normal form in the relational model, we want to show that DLNF generalizes BCNF. As Arenas and Libkin used a mapping from relational schemas to XML, we want to translate relational schemas to $\DLA$ knowledge bases (KB). It does not suffice to use the mapping from relational data into RDF graphs \cite{2012rdbmapping}, because it lacks means of translating the semantic information given in the relational schema. We will extend, similar to Sequeda et al.\ \cite{2012Sequeda}, the mapping from relational data into RDF graphs and introduce the \textit{Relational to Description Logic Direct Mapping} (R2DM). We can show for our direct mapping that any model of the translated KB corresponds to an instance of the relational schema. Our extension allows us then to show that this translated KB is in DLNF if the corresponding relational schema is in BCNF and vice versa.

\begin{paragraph}{Contributions.}
 The main contributions of this thesis are the following:
 \begin{itemize}
  \item \textbf{Relational to Description Logic direct mapping}: The direct-mapping of relational data to RDF \cite{2012rdbmapping} lacks means of mapping the semantic information available in the relational schema. Sequeda et al.\ already extended this direct mapping with semantic information \cite{2012Sequeda}. We will transfer their ideas to DLs and introduce in Section~\ref{ssec:dl_map_rdm} the \textit{relational to Description Logic direct mapping} (R2DM). The R2DM translates relational schemas into $\DLA$ KBs. Then it is possible to translate models of such KBs into instances of relational schemas and vice versa. We will show that any model of such a KB can be translated into an instance of the relational schema and vice versa.
  \item \textbf{Tree-based identification constraints}: In order to establish a normal form that is related to BCNF, we need to express dependencies over $\DLA$ KBs that resemble FDs over relational schemas. Calvanese et al.\ introduced path-based identification constraints \cite{2008calvanese} as such a formalism. In Section~\ref{ssec:dl_fd_sem} we will show that these do not properly capture FDs. Therefore, we introduce \textit{tree-based identification constraints} as a solution in Section~\ref{ssec:dl_fd_tidc}. Additionally, we will show that any FD of a relational schema can be translated into a tree-based identification constraint over a $\DLA$ KB and vice versa.
  \item \textbf{Description Logic Normal Form}: In Section~\ref{sec:dl_nf} we will investigate  redundancies in graph databases and establish a normal form for DLs. A $\DLA$ KB in \textit{Description Logic Normal Form} avoids redundancies. Additionally, we will compare in Section~\ref{sec:dl_bcnf} DLNF to BCNF. We will show that whenever a relational schema is in BCNF its translated $\DLA$ KB is in DLNF and vice versa.
 \end{itemize}
\end{paragraph}

\begin{paragraph}{State of the Art.}
\begin{itemize}
 \item Most of the research on the normalization of schemas in the relational model has been conducted in the 1970s and 1980s. In 1970 Codd introduced the relational model \cite{1970codd}. In this seminal paper he also coined the concept of normalization by giving a definition of what we today know as ``First Normal Form'' (1NF). Since then normal forms for relational data have been investigated. Codd developed Second and Third Normal Form (2NF and 3NF) \cite{1971codd, 1971codd2}. Additionally, Boyce-Codd Normal Form (BCNF) was introduced~\cite{1974codd}. So far, all normal forms have used functional dependencies for specifying semantic information on the data. Fagin introduced Fourth and Fifth Normal Form (4NF and 5NF) that avoid redundancies when multivalued and join dependencies are used \cite{1977fagin, 1979fagin}. Today even more normal forms exist. Among them are Domain/Key Normal Form (DKNF) \cite{1981fagin}, Sixth Normal Form (6NF) \cite{2002darwen} and more recently, Essential Tuple Normal Form (ETNF) \cite{2012darwen}. We will give a thorough introduction to the relational model, FDs, 3NF and BCNF in Chapter~\ref{ch:relational}.
 \item In 1998 the World Wide Web Consortium (W3C) introduced XML as a human- and machine-readable data format for the WWW \cite{2008xml,2006xml}. A first normal form for XML was developed by Embley and Mok \cite{2001embley}. This normal form is more restrictive than the normal form later introduced by Arenas and Libkin \cite{2002arenas, 2004arenas, 2006arenas}. To further investigate redundancies in relational data and XML documents Arenas and Libkin looked at these from an information-theoretic perspective  \cite{2003arenas}. Embley and Mok as well as Arenas and Libkin developed their own functional dependency language for XML documents. Additionally, both groups showed how to convert poorly designed into well-designed XML schemas. An additional language for functional dependencies in XML documents has been developed \cite{2002lee}. However, the authors have not considered the normalization problem with respect to the introduced dependencies. The model for XML documents together with XFDs and XNF as introduced by Arenas and Libkin will be recapitulated in Chapter~\ref{ch:xml}.
 \item Graph databases, introduced in the late 1980s \cite{1984kupervardi, 1987kunii}, are an active field of research today \cite{2013baeza,2013baeza2,2013libkin}. They play an important role in today's applications, for example the Semantic Web \cite{2001semanticweb, 2006semanticweb}. The development of the Semantic Web started in 2001. Since then the Resource Description Framework (RDF) \cite{2004rdf} has emerged as a standard for storage of Web data as a graph database. RDF Schema (RDFS) \cite{2004rdfs} and the Web Ontology Language (OWL) \cite{2004owl, 2012owl} make it possible to attach more semantic information to RDF data. The semantics of OWL2 \cite{2012owl} is given by an extension of the semantics of the DL $\SROIQ$ \cite{2012owl2semantics}. In addition to the standard semantics of OWL2, the W3C defined OWL2 profiles tailored for specific purposes \cite{2012owl2prof}. OWL2 QL was defined to be used with large volumes of instance data, as nowadays available in DBMS. At the core of OWL2 QL is the description logic $\DLA$ \cite{2006calvanese}, a member of the $\DL$ family \cite{2009artale}.
 This makes description Logics \cite{2003baader} well-suited for managing data repositories \cite{2011lenzerini}. In particular, DLs are a natural language for constraints over graph databases \cite{2013calvanese2}. Many extensions \cite{2001calvanese,2008calvanese} to classic DLs are available that are tailored towards specific applications \cite{2007calvanese}.
 
 Several formalisms for expressing functional dependencies have been investigated in DLs. Among them, Calvanese et al.\ introduced identification constraints \cite{2001calvanese} and extended them with path-based identification constraints \cite{2008calvanese}. A more restrictive form of FDs in DLs is investigated in \cite{2009romero}. They only consider FDs in DLs over functional paths. To the best of our knowledge there is no research on normal forms regarding these types of FDs in DLs. 
\end{itemize}  

\end{paragraph}


\begin{paragraph}{Organization.}
 This thesis is organized as follows. We will investigate redundancies and normal forms in each of the three introduced data models. Therefore, this thesis has three chapters, each of which focuses on a particular data model. Chapter~\ref{ch:relational} discusses normal forms for the relational model, chapter~\ref{ch:xml} summarizes the normal form for XML documents introduced by Arenas and Libkin \cite{2004arenas}. In Chapter 4 we will finally present a new normal form for DLs. Each chapter has the following sections: First, we will introduce the ``Preliminaries'' for the particular data model. Then, we show how to map relational schemas to schemas of the particular model. Next, we investigate data dependencies. Then, we will introduce normal forms and show their correlation to BCNF. Finally, the last section of each chapter is devoted to a short summary. Chapter~\ref{ch:conclusion} will then review this work and give an outlook to further work in this area.
\end{paragraph}